package com.unionfind_01;

/**
 * @Author: tgy
 * @Date: 1/12/21 6:32 PM
 *
 * 路径减半
 *
 *    A
 *    \
 *    B
 *    \
 *    C
 *    \
 *    D
 *    \
 *    E
 *
 *  从当前接点开始，每隔一个节点都指向其祖父节点
 *
 *            A
 *          /  \
 *         B   C
 *           /  \
 *          D   E
 *
 */
public class UF_QuickUnion_Rank_PathHalving  extends UF_QuickUnion_Rank{

    public UF_QuickUnion_Rank_PathHalving(int size) {
        super(size);
    }


    @Override
    public int find(int v) {

        while (parents[v] != v) {

             parents[v] = parents[parents[v]];
             v = parents[v];
        }

        return v;
    }

    public static void main(String[] args) {

        UF_QuickUnion quickUnion = new UF_QuickUnion_Rank_PathHalving(9);


        quickUnion.union(1,3);
        quickUnion.union(2,8);
        quickUnion.union(4,7);
        quickUnion.union(3,4);
        quickUnion.union(1,2);
        quickUnion.union(8,5);


        System.out.println(quickUnion.isSame(1, 4));

    }
}
